/*
    题目思路：
    后序遍历二叉树，根据左右孩子的状态来决定当前节点的状态。
    0 = 当前节点未被覆盖
    1 = 当前节点放置了摄像头
    2 = 当前节点已被覆盖
*/

// step 1# 后序遍历函数：返回节点状态，并更新摄像头数量
int traversal(struct TreeNode* node, int* ans) {
    // step 1.1# 递归终止条件：空节点，视为已被覆盖（返回2）
    if (!node)
        return 2;

    // step 1.2# 递归遍历左右子节点
    int left = traversal(node->left, ans);
    int right = traversal(node->right, ans);

    // step 1.3# 如果左右子节点都被覆盖（2），当前节点未被覆盖，返回0
    if (left == 2 && right == 2) {
        return 0;
    }

    // step 1.4# 如果左右子节点有任一未被覆盖（0），当前节点必须放摄像头
    if (left == 0 || right == 0) {
        (*ans)++; // 放置一个摄像头
        return 1;
    }

    // step 1.5# 如果左右子节点有摄像头（1），当前节点被覆盖
    if (left == 1 || right == 1)
        return 2;

    // step 1.6# 正常逻辑不会走到这里
    return -1;
}

// step 2# 主函数：求最少需要多少个摄像头
int minCameraCover(struct TreeNode* root) {
    int ans = 0;

    // step 2.1# 遍历整棵树，如果根节点未被覆盖，需要额外放置一个摄像头
    if (traversal(root, &ans) == 0)
        ans++;

    // step 2.2# 返回所需摄像头数量
    return ans;
}
